package 我的Java学习_算法基础.day_03;

import static 我的Java学习_算法基础.day_01.唯一成对的数.printArray;

public class _046_构造小顶堆 {
    public static void main(String[] args) {
        int[] a = {8,5,10,7,4,9,7,2,23};
        makeMinHeap(a);
        printArray(a);
    }
    public static void makeMinHeap(int[] array){
        int n = array.length;
        for(int i = n/2-1;i>=0;i--){ //这些节点的子树已经是合法的最小堆
            minHeapFixDown(array,i,n);
        }
    }
    //假设某个节点的左右子树分别满足最小堆，现在检测整体是否满足
    //如果节点不满足向下沉，将他的最小子节点上浮
    private static void minHeapFixDown(int[] array,int i ,int length){
        int j = 2* i+1;   //左孩子
        int temp = array[i];
        while(j<length){
            if(j+1<length&&array[j+1]<array[j]){    //在左右孩子中，找最小的
                j++;    //小孩子
            }
            if(array[j]<temp){  //小孩子比自己还小，则孩子上浮
                array[i] = array[j];
                i = j;      //站在小孩子的位置，大孩子可以不用管了（没有变动）
                j = 2*i+1;  //指向小孩子的左孩子
            }else{
                break;
            }
        }
        //循环完，i的位置就是temp该放的位置
        array[i] = temp;
    }
}
